package codingforgreat.lchot150;

import java.util.PriorityQueue;

public class Lc295 {
    class MedianFinder {
        PriorityQueue<Integer> smallQueue;
        PriorityQueue<Integer> bigQueue;
        public MedianFinder() {
            smallQueue = new PriorityQueue<>((a,b) ->{return a - b;});
            bigQueue = new PriorityQueue<>((a,b) ->{return b - a;});
        }

        public void addNum(int num) {
            if(bigQueue.isEmpty() || num <= bigQueue.peek()){
                bigQueue.add(num);
            }else{
                smallQueue.add(num);
            }
            balanced();
        }
        public void balanced(){
            if(Math.abs(bigQueue.size() - smallQueue.size()) == 2){
                if(bigQueue.size() > smallQueue.size()){
                    smallQueue.add(bigQueue.poll());
                }else{
                    bigQueue.add(smallQueue.poll());
                }
            }
        }

        public double findMedian() {
            if(smallQueue.size() > bigQueue.size()){
                return (double)smallQueue.peek();
            }else if(bigQueue.size() > smallQueue.size()){
                return (double)bigQueue.peek();
            }else{
                return (double)((double)(smallQueue.peek() + bigQueue.peek())/2);
            }

        }
    }
}
